#define _CRT_SECURE_NO_WARNINGS

class Solution {
public:
    void backtrace(vector<vector<int>>& vv, vector<int>& v, int& n, int& k)
    {
        if (k == 0)
        {
            vv.push_back(v);
            return;
        }
        for (int i = 1; i <= n; i++)
        {
            int flag = 0;
            for (int j = 0; j < v.size(); j++)
            {
                if (v[j] >= i)
                {
                    flag = 1;
                    break;
                }
            }
            if (flag == 1)
                continue;
            v.push_back(i);
            --k;
            backtrace(vv, v, n, k);
            v.pop_back();
            ++k;
        }
    }
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> vv;
        vector<int> v;
        backtrace(vv, v, n, k);
        return vv;
    }
};

class Solution {
public:
    void backtrace(vector<vector<int>>& vv, vector<int>& v, int& n, int& k, int start)
    {
        if (k == 0)
        {
            vv.push_back(v);
            return;
        }
        for (int i = start; i <= n; i++)
        {
            v.push_back(i);
            --k;
            backtrace(vv, v, n, k, i + 1);
            v.pop_back();
            ++k;
        }
    }
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> vv;
        vector<int> v;
        int start = 1;
        backtrace(vv, v, n, k, start);
        return vv;
    }
};

class Solution {
public:
    void backtrace(vector<vector<int>>& vv, vector<int>& v, int& n, int& k, int start)
    {
        if (k == 0)
        {
            vv.push_back(v);
            return;
        }
        for (int i = start; i <= n - k + 1; i++)
        {
            v.push_back(i);
            --k;
            backtrace(vv, v, n, k, i + 1);
            v.pop_back();
            ++k;
        }
    }
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> vv;
        vector<int> v;
        int start = 1;
        backtrace(vv, v, n, k, start);
        return vv;
    }
};

